思路：
AC自动机模板题。AC自动机是在一个字符串中查找多个特征串的算法。其中使用了一个next数组和Trie树，与kmp的next数组相类似。思想就是当指向的节点不匹配时，退回上一个匹配的节点，然后在其fail节点中继续查找这个串。（可以理解为两个特征串相同的前后缀然后直接跳转）构造fail指针的时候，需要查找其父节点的fail然后查其儿子节点。利用BFS完成。在扫描的时候，需要对已经扫过的节点标记为-1，避免重复计算。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
using namespace std;
struct node {
node *next[26];
node *fail;
int sum;
node() {
for (int i = 0;i < 26;i++)next[i] = NULL;
sum = 0;//字符串末尾数量
}
};
//Build Trie-Tree
void insert(node *root, string str) {
node *p = root;
for (int i = 0;i < str.length();i++) {
int id = str[i] - 'a';//id
if (p->next[id] == NULL) {
node *q = new node;
p->next[id] = q;
}
p = p->next[id];
}
p->sum++;
}
//Build fail pointer
void buildfail(node *root) {
node *p = root;
queue<node*> q;
root->fail = NULL;
//对深度为2的节点fail初始化为root，不然会指向自己
for (int i = 0;i < 26;i++) {
if (root->next[i] != NULL) {
root->next[i]->fail = root;
q.push(root->next[i]);
}
}
while (!q.empty()) {
node *t = q.front();
q.pop();
for (int i = 0;i < 26;i++) {
if (t->next[i] != NULL) {
q.push(t->next[i]);
p = t->fail;
//为什么要有这个循环？因为没有的话只会查找一个fail节点，但实际上还有很多其它的fail节点的儿子没查
while (p!=NULL) {
if (p->next[i]!=NULL) {
t->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if(p==NULL)t->next[i]->fail = root;
}
}
}
}
//AC-automation
int acauto(node *root,string str) {
int ans = 0;
node *p = root;
for (int i = 0;i < str.length();i++) {
int id = str[i] - 'a';
//先匹配一个
while (!p->next[id] && p != root)p = p->fail;
p = p->next[id];
if (!p) p = root;
node *temp = p;
//为了尝试匹配所有情况
while (temp != root) {
if (temp->sum >=0) {
ans += temp->sum;
temp->sum = -1;
}
else break;
temp = temp->fail;
}
}
return ans;
}
void freetree(node *root) {
node *p = root;
if (p == NULL)return;
else {
for (int i = 0;i < 26;i++) {
if (p->next[i] != NULL)freetree(p->next[i]);
}
delete[] p;
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T,n;
cin >> T;
while(T--) {
cin >> n;
string str;
node *root = new node;
for (int i = 0;i < n;i++) {
cin >> str;
insert(root, str);
}
buildfail(root);
cin >> str;
cout << acauto(root,str) << "\n";
freetree(root);
}
return 0;
}